VOLE(Vector Oblivious Linear Evaluation) & VOLE based ZK
1.概要
以下の図のように二者間でお互いの情報を隠したまま線形演算を行うことからOblivious Linear Evaluation:OLEと呼ばれている。
VOLEはa,bおよびyがベクトルになったOLEであり、n OLE行うよりも構成しやすい。
https://scrapbox.io/files/6757a8beace672db92632ca6.pnghttps://scrapbox.io/files/6757a8fe01ab25d7a220184a.png
https://scrapbox.io/files/67712ee9698ebcb6770e0b04.png
具体的にはProverとVerifierは協力してVOLEを構成する。
2 VOLE commitment shecme
VOLEのcommitment shcemeは二つのフェーズに別れている
Setup: VOLEプロトコルを用いて N 個のVOLE相関を生成します。このプロトコルの通信コストは N に対して多項対数的で、例えば N=10^7 の場合、1つのVOLE相関を生成する平均時間は20ナノ秒未満です。
LPN+GGMはsetup
Online: プルーバーが N 個のフィールド要素を送信してコミットメントを生成します。このフェーズでは通信コストは N に対して線形ですが、計算コストは低く、フィールド要素の加算と乗算のみが必要です。
既存の加法的同型性を持つ非インタラクティブコミットメントは公開鍵操作に依存しており、コミットおよびオープン操作に大きな計算負荷がかかる。VOLEベースのスキームは、非インタラクティブ性を犠牲にする代わりに、効率的で軽量な計算を実現できる。ただし、Fiat-SchamirによりNon Interactiveに変換することもできる 2.2 OR gate
VOLEはHindingとBindingだけでなくAdditive homomorphismも有している点が特徴
これによりcommitされた値に対して追加のcommunicationを必要とせずにlinear operaton(transformation)を実現できるので、逐次的に行われる加算(OR gate)の評価を効率的に処理できる。具体的にはまずProverがinput layerの値をcommitする。verifeirは各Layerの遷移(中間値の処理)をAdditive homomorphicにlinear transformationしていくことで評価することができるため、余計なcommunicationが生まれない。
以下のスライドのようにpublic value$ \alphaと$ \betaを導入することで表現できる。
https://scrapbox.io/files/67715c110d58134731df1ca7.png
乗算(AND gate)の場合は演算結果の多項式次数が2になってしまうので、工夫が必要になる(後述)
2.3 ANDゲート
加算ゲートの出力に対するコミットメントは同型性により効率的にできるが、乗算(AND gate)に関しては工夫が必要である。
なぜなら一次多項式どうしの積は二次多項式となるため、VOLEの方程式を満たさない。
そこでtransformationやbatchを組み合わせた効率化が提案されている。
https://scrapbox.io/files/677162e3767e4ac822d2af5e.png
より具体的には、証明者と検証者は2種類のワイヤ（i）回路の入力ワイヤと（ii）ANDゲートの出力ワイヤに対してコミットメントを生成する。XORゲートの出力線に対するコミットメントは、I加法的同相特性により、証明者と検証者によって局所的に生成される。
ゲートへの入力線は、回路入力または他のゲートの出力であるため、タイプ(i)と(ii)でカバーされる。同様に、回路出力はタイプ(ii)でカバーされる。
参考資料